package Genericity;

import java.util.*;
class Node{
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class TestMap_Set {
    /**
     * 求的是出现次数最多的单词
     *
     * @param words
     * @param k
     * @return
     */
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        //1:统计每个单词出现的次数，map
        for (String s : words) {
            if (map.get(s) == null) {
                map.put(s, 1);
            } else {
                int val = map.get(s);
                map.put(s, val + 1);
            }
        }
        //2:建立一个大小为k的小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getValue().compareTo(o1.getValue());
                }
                return o1.getValue() - o2.getValue();
            }
        });

        //3:遍历map
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                //说明堆中已经放满了k个要比较堆顶元素和当前的数据大小的关系
                Map.Entry<String, Integer> top = minHeap.peek();
                //判断频率是否相同，如果相同比较单词的大小，单词大的入堆
                if (top.getValue().compareTo(entry.getValue()) == 0) {
                    if (top.getValue().compareTo(entry.getValue()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                } else {
                    if (top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        return null;
    }





    public static void func4(String strExce,String strActual){
        HashSet<Character> set=new HashSet<>();
        for (char ch: strActual.toUpperCase().toCharArray()) {
            set.add(ch);
        }
        HashSet<Character> broken=new HashSet<>();
        for (char ch:strExce.toUpperCase().toCharArray()) {
            if (!set.contains(ch)&&broken.contains(ch)){
                System.out.println(ch);
                broken.add(ch);
            }
        }
    }

    public int numJewelsInStones(String jewels,String stong){
        //石头中找宝石问题
        HashSet<Character> set=new HashSet<>();
        for (Character ch:jewels.toCharArray()) {
            set.add(ch);
        }
        int count=0;
        for (Character ch: stong.toCharArray()) {
            if (set.contains(ch)){
                count++;
            }
        }
        return count;
       

    }

    public Node copyRandomList(Node head){
        //复制随机指针的链表
        Map<Node,Node> map=new HashMap<>();
        Node cur=head;
       while (cur!=null){
           Node node=new Node(cur.val);
           map.put(cur,node);
           cur=cur.next;
       }
        cur=head;
        while (cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
        }
        return map.get(head);
    }


    public int singLeNumber(int[] nums){
        //找出数组中只出现一次的数值，正确解法是用异或
        HashSet<Integer> set=new HashSet<>();
        for (int x: nums) {
            if (set.contains(x)){
                set.remove(x);
            }else{
                set.add(x);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])){
                return nums[i];
            }
        }
        return -1;
    }
    public static int func3(int[] array){
        HashSet<Integer> set=new HashSet<>();
        for (int x:array) {
            if (set.contains(x)){
                return x;
            }else {
                set.add(x);
            }
        }
        return -1;
    }
    public static Set<Integer> func2(int[] array){
        HashSet<Integer> set=new HashSet<>();
        for (int x:array) {
            set.add(x);
        }
        return set;
    }


//    key是关键字 val是出现的次数
    public static Map<Integer,Integer> fun(int[] array){
        Map<Integer,Integer> map=new HashMap<>();
        //判断array中的元素是否在map当中，不在就是1，在就加一
        //自己写的
      /*  for (int i = 0; i < array.length; i++) {
            if (!map.containsKey(array[i])){
                map.put(array[i],1);
            }else {
                map.put(array[i],map.get(array[i])+1);
            }
        }*/
        for (int x:array) {
            if (map.get(x)==null){
                map.put(x,1);
            }else {
                int val=map.get(x);
                map.put(x,val+1);
            }
        }
        return map;

    }
    public static void main(String[] args) {
        int[] array=new int[1_0000];
        Random random=new Random();
        for (int i = 0; i < array.length; i++) {
            array[i]=random.nextInt(1000);
        }
        Map<Integer,Integer> map=fun(array);
        System.out.println(map);
    }

    /**
     * Set特点：自动去重
     * @param args
     */
    public static void main2(String[] args) {
        Set<Integer> set=new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(1);
        System.out.println(set);

    }
    /**
     * hashmap存储元素的时候，是按照哈希函数来存储的
     * @param args
     */
    public static void main1(String[] args) {
        Map<String,Integer> map=new HashMap<>();
        map.put("abc",3);
        map.put("bit",2);//put在存储元素的时候，k如果相同，val值会被覆盖
        map.put("hello",4);
        System.out.println(map);
        System.out.println(map.get("bit"));//通过key值获取对应的val值
        Set<String> set=map.keySet();//set这个集合中元素都是不重复的
    }
}
